package com.leetcode.sort;

import java.util.Arrays;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-19 13:34
 * @version: 1.0
 * @description: 归并排序
 **/
public class MergeSort {
    public int[] sortArray(int[] nums) {
        mergeSort(nums,0,nums.length-1);
        return nums;
    }

    private void mergeSort(int[] arr, int left, int right) {

        if (left >= right)
            return;

        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid + 1, right);

    }

    private void merge(int[] arr, int left, int mid, int right) {
        //定义两个数组，存放要排序的元素
        int[] arrLeft = new int[mid - left];
        int[] arrRight = new int[right - mid + 1];
        //赋值
        for (int i = 0; i < arrLeft.length; i++) {
            arrLeft[i] = arr[left + i]; //注意：赋值时注意，不是每次都从零开始
        }
        for (int i = 0; i < arrRight.length; i++) {
            arrRight[i] = arr[mid + i]; //注意：赋值时注意，不是每次都从零开始
        }
        int l = 0,r = 0,k = left;//注意：这里的大数组的角标，每次要与left一致，不是从零开始
        while (l < arrLeft.length && r < arrRight.length){
            if (arrLeft[l] < arrRight[r]){
                arr[k++] = arrLeft[l++];
            }else {
                arr[k++] = arrRight[r++];
            }
        }
        while(l < arrLeft.length){
            arr[k++] = arrLeft[l++];
        }
        while(r < arrRight.length){
            arr[k++] = arrRight[r++];
        }
    }

    public static void main(String[] args) {
        //归并排序是将两个有序的数组合并成一个有序数组的过程
        int[] arr = {2,7,5,3,6,1,9,8,10};
        MergeSort mergeSort = new MergeSort();
        mergeSort.mergeSort(arr,0 ,arr.length-1 );
        System.out.println(Arrays.toString(arr));
    }

}
